1. Field of the Invention
The present invention relates generally to a digital date transmission system using error-correcting (or error control) codes, and more specifically to techniques for determining a maximum metric and thereafter specifying a most likely code word corresponding thereto in a decoder provided in such a system.
2. Description of Related Art
It is known in the art that in order to reliably reproduce information sequences transmitted over a noisy channel, a wide variety of error control coding/decoding techniques using block codes or convolutional codes have been proposed.
Prior to turning to the present invention, it is deemed preferable to briefly describe, with reference to FIGS. 1-5, a conventional digital data transmission system using block codes so as to combat noisy transmission environments.
FIG. 1 is a block diagram showing a simplified example of a transmitter 10 which is provided in a typical digital data transmission system and which utilizes block codes for the purposes of error-correcting coding. Since the transmitter 10 itself is well known in the art, and accordingly, only a brief description thereof will be given. An encoder (channel encoder) 12 is supplied with an information sequence U and divides the same into message blocks of a fixed bit length each. For the sake of simplifying the descriptions, it is assumed that each message block is represented by a binary 4-tuple called a message, and hence there are 24 (=16) different possible messages (depicted by U(1)-U(16)). The encoder 12 transforms the messages U(1)-U(16) independently into code words C(1)-C(16) on a one-to-one basis using a coding table 14 listed below the encoder 12.
A modulator 16 receives successively the code words outputted from the encoder 12 and translates them into corresponding analog baseband signal 18. Following this, an up-converter 20 converts, using a local oscillator (not shown), the analog base-band signal 18 to an operating frequency of the transmitter 10 in preparation for transmission, after which the code modulated high-frequency signal is radiated to the destination via an antenna 22.
FIG. 2 is a block diagram schematically showing a simplified example of a receiver (depicted by 24). The code modulated high-frequency signal, transmitted from the transmitter 10, is applied to a down-converter 26 by way of an antenna 25. The down-converter 26 operates such as to convert the incoming high-frequency signal to the corresponding analog baseband signal using a local oscillator (not shown). The analog baseband signal is applied to a demodulator 28, which in turn generates a demodulated received signal R. A decoder (i.e., channel decoder) 30 is supplied with the signal R, estimating an original code word and generating the estimate as a reproduced information sequence.
Referring to FIG. 3, the decoder 30 (FIG. 2) is shown in detail in terms of configuration thereof. As illustrated, the decoder 30 is comprised of a memory 40, a plurality of metric calculators 42(1)-42(16) which are identical with each other in both configuration and function, a most likely code word determiner 44, and a code converter 46. The metric calculators 42(1)-42(16) are respectively supplied with the code words C(1)-C(16) previously stored in the memory 40 and identical to those used in the transmitter 24, and also supplied with the received signal R which has been demodulated at the demodulator 28 of FIG. 2. Each of the metric calculators 42(1)-42(16) calculates a metric which is a measure of the closeness of the received signal R to the corresponding code word (viz., one of C(1)-C(16)), and applies a corresponding metric (viz., one of M(1)-M(18)) to the most likely cord word determiner 44. This determiner 44 searches the maximum metric among the metrics M(1)-M(16) applied thereto, and determines one code word corresponding to the maximum metric, the operation of which will be further described later. The code word thus determined, viz., the output of the determiner 44, is depicted by D(15), and is subject to code conversion at the code converter 46 and outputted therefrom as a reproduced information sequence.
FIG. 4 is a block diagram showing the detail of the most likely code word determiner 44 (FIG. 3) which comprises a plurality of selectors 50(1)-50(15). In brief, the determiner 44 operates such as to detect the maximum metric among the inputted metrics M(1)-M(16) in a tournament-like manner until only one remains, and then determine and generate the most likely code word (one of C(1)-C(16)) corresponding to the detected maximum metric.
The selectors 50(1)-50(15) are substantially identical with each other in both configuration and function, and as such, the selector 50(1) is mainly described. As shown in FIG. 4, the selector 50(1) receives two pairs of {M(1), C(1)} and {M(2), C(2)}, comparing the received metrics of M(1) and M(2), and selecting and outputting either pair with the larger metric. The pair (viz, {M(1), C(1)} or {M(2), C(2)}) selected at the selector 50(1) is depicted by {N(1), D(1)}. More specifically, if the selector 50(1) selects the pair {M(1), C(1)}, the output N(1) equals M(1), and the output D(1) equals C(1).
Each of the remaining selectors 50(2)-50(15) operates in exactly the same manner as the selector 50(1) and outputs the corresponding pair {N(k), D(k)} (k=2, 3, . . . 15). The rightmost selector 50(15) eventually determines one pair, wherein the metric (=N(15)) exhibits the maximum value and wherein the cord word D(15) corresponds to the maximum metric N(15) and is regarded as the most likely code word. Note that the metric N(15) outputted from comparator 50(15) has done the job and thus will not used in the subsequent processing. The code word D(15) thus detected corresponds to one of the cord words C(1)-C(16) and applied to the code converter 46 (FIG. 3), whereat the code word is converted to the corresponding information sequence (depicted by U) as mentioned above.
The selector 50(1) of FIG. 4 will further be described with reference to FIG. 5. As shown in FIG. 5, the selector 50(1) is comprised of a comparator 52 and two selectors 54 and 56. The comparator 52 compares the two metrics M(1) and M(2), and applies the comparison result to the selectors 54 and 56. The selector 54 responds to the comparison result and selects M(1) as N(1) if M(1)xe2x89xa7M(2), and selects M(2) as N(1) if M(1) less than M(2). On the other hand, the selector 56 is responsive to the comparison result and outputs C(1) as D(1) if M(1)xe2x89xa7M(2), and output C(2) as D(1) If M(1) less than M(2).
Returning to FIG. 4, the most likely code word determiner 44 is provided with four (4) stages for selecting the larger metric each, because it has been assumed that each message is a binary 4-tuple. In general, if Q represents the different possible messages to be transmitted, the number of the metric selecting stages at the determiner 44 is given by log2Q. Namely, the number of the metric selecting stages of the determiner 44 increases with increase in the different possible messages to be transmitted. On the other hand, the computation at each stage of the determiner 44 accompanies the comparing operation, which inevitably incurs a relatively large delay. Accordingly, the aforesaid conventional techniques for determining the most likely code word has encountered the problems that it is practically not applicable to a system that requires a very high transmission speed. By way of example, with the Viterbi decoder, the value of Q is typically limited to a range of 24 to 27 because if Q is made larger that that, it is impossible to realize a practically available decoder due to the slow speed of decoding operations.
It is therefore an object of the present invention to provide an apparatus, provided in a decoder of error-correcting codes, which is able to rapidly determine a most likely code word with a small amount of computations compared to the conventional technique.
Another object of the present invention is to provide a method of determining a most likely code word in a decoder of error-correcting codes at a high speed compared to the conventional technique.
In brief, these objects are achieved by the techniques wherein, in order to rapidly determine a most likely code word at a decoder provided in a digital data transmission system using block codes or convolutional codes for the purposes of combating a noisy channel environment, an adaptively controllable threshold is introduced so as to discriminate a largest metric with a small amount of computations. The metric is the measure of closeness of a signal transmitted to the decoder to one of plural code words previously stored in the decoder. A counter counts the number of metrics each exceeding the threshold, and informs a controller of the count result. If the count result is more than one, the controller raises the threshold, on the contrary, if the count result is zero then the controller lowers the threshold, both are performed in an effort to narrow down one metric in excess of the threshold. The threshold thus adaptively controlled is compared with each of plural metrics. If the count result becomes one, it implies that the largest metric has been determined. Subsequently, a code word corresponding to the largest metric is regarded as the most likely code word.
One aspect of the present invention resides in a most likely code word determiner provided in a decoder of a digital data transmission system using error-correcting codes for combating noisy environments, comprising a plurality of comparators which respectively receive a plurality of metrics each indicating closeness of a corresponding code word to a signal transmitted to the decoder, the plurality of comparators respectively comparing the plurality of metrics with a threshold and generating a plurality of comparison results. A counter coupled to receive the plurality of comparison results, counting a number of comparison results each of which indicates that the corresponding metric exceeds the threshold, and generating a count result indicating that the number of comparison results is zero or one or more than one. Further, a controller coupled to receive the count result and issuing an acknowledge signal indicating that the count result is zero or one or more than one, the controller changing the threshold if the count result is zero or more than one and applying the changed threshold to the plurality of comparators. A selector coupled to receive the plurality of comparison results and a plurality of code words previously prepared in the decoder, the selector selecting a code word which is defined as the most likely code word if the acknowledge signal indicates that the count result is one.
Another aspect of the present invention resides in a method of determining a most likely code word in a decoder of a digital data transmission system using error-correcting codes for combating noisy environments, comprising the steps of: (a) receiving a plurality of metrics each indicating closeness of a corresponding code word to a signal transmitted to the decoder, comparing the plurality of metrics with a threshold, and generating a plurality of comparison results; (b) receiving the plurality of comparison results, counting a number of comparison results each of which indicates that the corresponding metric exceeds the threshold, and generating a count result indicating that the number of comparison results is zero or one or more than one; (c) receiving the count result and issuing an acknowledge signal indicating that the count result is zero or one or more than one, changing the threshold if the count result is zero or more than one and generating the changed threshold which is used at step (a); and (d) receiving the plurality of comparison results and a plurality of code words previously prepared in the decoder, and selecting a code word which is defined as the most likely code word if the acknowledge signal indicates that the count result is one.
Still another aspect of the present invention resides in a most likely code word determiner provided in a decoder of a digital data transmission system using error-correcting codes for combating noisy environments, comprising a plurality of metric calculators for respectively calculating a plurality of metrics each indicating closeness of a corresponding code word to a signal transmitted to the decoder, and accumulating the calculated metrics and storing same therein, each of the plurality of metrics being represented by a sign bit and an absolute value. Further, a counter coupled to receive the sign bits, counting a number of sign bits each indicating a non-negative sign bit, and generating a count result indicating that the number of the non-negative sign bits is zero or one or more than one. A controller coupled to receive the count result and issuing an acknowledge signal indicating that the count result is zero or one or more than one, the controller operating such as to add a predetermined value to each of the accumulated metrics if the count result is zero, and subtract the predetermined value from each of the accumulated metrics if the count result is more than one. A selector coupled to receive the sign bits and a plurality of code words previously prepared in the decoder, the selector selecting a code word which is defined as the most likely code word if the acknowledge signal indicates that the count result is one.
Still another aspect of the present invention resides in a method of determining a most likely code word in a decoder of a digital data transmission system using error-correcting codes for combating noisy environments, comprising the steps of: (a) calculating a plurality of metrics each indicating closeness of a corresponding code word to a signal transmitted to the decoder, and accumulating the calculated metrics and storing same, each of the plurality of metrics being represented by a sign bit and an absolute value; (b) receiving the sign bits, counting a number of sign bits each indicating a non-negative sign bit, and generating a count result indicating that the number of the non-negative sign bits is zero or one or more than one; (c) receiving the count result and Issuing an acknowledge signal indicating that the count result is zero or one or more than one, adding a predetermined value to each of the accumulated metrics if the count result is zero, and subtracting the predetermined value from each of the accumulated metrics if the count result is more than one; and (d) receiving the sign bits and a plurality of code words previously prepared in the decoder, and selecting a code word which is defined as the most likely code word if the acknowledge signal indicates that the count result is one.